This section proposes a 4-step approach to solve the aforementioned problem. The details of each step are later explained in the following sections.
\begin{figure}[h!]
\centering
\includegraphics[scale=0.4]{figures/unify-crop.pdf}
\caption{Overview of the framework} 
\label{fig:overview}
\end{figure}
\subsubsection*{Step 1: Modeling the availability of the bus}
Section~\ref{sec:bus_availability} first shows how to model the availability of the bus to task $\tau_i$ using a general framework $\BusAvailability{i} = \left\langle \Tmin{i}{}, \Tmax{i}{} \right\rangle$. The functions $\Tmin{i}{j}$ and $\Tmax{i}{j}$ represent the earliest and latest time instants at which the bus can be available to $\tau_i$ for the $j$'th time.
%, i.e the earliest and latest instant of the $j$'th bus slot available to $\tau_i$ (called $j$'th free bus slot hereafter). 
The implementation of these functions depends on the particular arbitration policy and the request profiles of all the tasks running on the other cores. 
%Section~\ref{sec:bus_availability} explains the computation of these functions for two different arbitration policies.

\subsubsection*{Step 2: Compute worst-case cumulative delay}
Given the model of availability of the bus  computed in Step~1, a specific request $\request{i}{k}$ from $\tau_i$ and a given slot assignment for that request, we propose a mechanism to compute the maximum delay that the \emph{single} request can suffer when scheduled in that slot. We then extend the same approach to compute the cumulative delay for a \emph{sequence} of requests, assuming a given request-to-slot assignment for each of them (i.e. a 1:1 mapping of the requests to free bus slots). 
% we next design and prove the correctness of Algorithm~\ref{algo:MaxDelay} to compute the maximum cumulative delay that can be incurred by all the requests of $\tau_i$ during its execution \emph{for a given ``request-to-free-bus-slot'' assignment}.
Formally, we model a request-to-slot assignment as a function $\Assignment{i}{}$ such that, $\forall r \in [1, \NbReqPerTask{i}]$, 
the $r$'th request generated by $\tau_i$ is served in the $\Assignment{i}{r}$'th bus slot available to task $\tau_i$. Then, assuming a given \emph{request-to-slot mapping} $A = \{\Assignment{i}{1}, \Assignment{i}{2}, \ldots, 
\Assignment{i}{\NbReqPerTask{i}} \}$, we find the release time and service time ($\reqrel{i}{k}$ and $\reqserv{i}{k}$), for all requests $\request{i}{k}$ of task $\tau_i$ that maximizes the cumulative delay of all the requests.
Figure~\ref{fig:reqslot} illustrates the request-slot assignment table and a possible mapping of requests to slots. If request $k$ is assigned to slot $j$, subsequent requests ($>k$) may only occuper higher slots ($>j$). 
\begin{figure}[h!]
\centering
\includegraphics[scale=0.3]{figures/reqslotmodel-crop.pdf}
\caption{Request to slot assignment. Grey boxes indicate feasible slots} 
\label{fig:reqslot}
\end{figure}
%i.e. $\sum_{k=1}^{\NbReqPerTask{i}} (\reqserv{i}{k} - \reqrel{i}{k})$ is maximum. 
Determining these values is complicated by the constraints imposed 
on these $2 \NbReqPerTask{i}$ variables, including (1) single outstanding request assumption (for all requests $\request{i}{k}$, we have $\reqrel{i}{k} > \reqserv{i}{k-1}$) and (2) maximum slot availability constraint --
In compliance with this assumption, $\reqserv{i}{k} \leq \Tmax{i}{\Assignment{i}{k}}$, because if request $k$ is served in the $\Assignment{i}{k}$'th free slot then $\reqserv{i}{k}$ cannot be greater than the latest time at which that slot can be free. 
 Determining these values is complicated by the constraints imposed 
 on these variables, such as: (1) Single outstanding request assumption -- For all requests $\request{i}{k}$, we have $\reqrel{i}{k} > \reqserv{i}{k-1}$ and (2) Slot availability constraint -- A request served in slot k will 
 be served no later than the latest time at which the slot can be free or formally $\reqserv{i}{k} \leq \Tmax{i}{\Assignment{i}{k}}$. 
 This step is discussed in detail in Section~\ref{sec:wc_delay}.
 
%  In compliance with this assumption, $\reqserv{i}{k} \leq \Tmax{i}{\Assignment{i}{k}}$, because if request $k$ is served in the $\Assignment{i}{k}$'th free slot then $\reqserv{i}{k}$ cannot be greater than the latest time at which that slot can be free. 



\subsubsection*{Step 3: Finding the worst-case assignment}
In this step, we propose an algorithm (in Section~\ref{sec:wc_assignment}) to determine a request-to-slot mapping $A$ for task $\tau_i$ that maximizes the cumulative delay of all its $\NbReqPerTask{i}$ requests. To do so, our technique first computes an upper bound, $\TaskUBslot{i}$, on the number of free bus slots that can possibly be used by task $\tau_i$.
This upper bound gives us a range $[1,\TaskUBslot{i}]$ of free bus slots within which we know that all the requests of the analyzed task $\tau_i$ are served. 
% A naive approach to maximize the cumulative delay incurred by the requests of $\tau_i$ is to apply a brute force approach, i.e. all the request-to-slot mappings $A$ are explored and a cumulative delay is computed for each of them by using the method proposed in Step 2; At the end, only the largest delay is returned. However, such a method does not scale and is computationally inefficient due to the exhaustive exploration of all the possible mappings.  
%such that, for all requests $\request{i}{r}$ with $r \in [1, \NbReqPerTask{i}]$, $\Assignment{i}{r} \leq \TaskUBslot{i}$ (i.e. the request $\request{i}{r}$ uses a free bus slot within the admissible 
%range of bus slots) and $\Assignment{i}{r} > \Assignment{i}{r-1}$ (i.e. request $\request{i}{r}$ is not served before request $\request{i}{r-1}$). But this naive solution is of exponential complexity. 
Instead of an exhaustive exploration of all request to slot mappings, we reduce the complexity of the problem by eliminating, at early stage of the analysis, the request-to-slot mappings that cannot possibly lead to the worst-case delays. This improvement substantially reduces the time-complexity of the proposed solution.
% and, based on those properties, we show that our algorithm $name2$ finds an assignment $\Assignment{i}{}$ that maximizes $name(\Assignment{i}{})$ in a time complexity $O(\NbReqPerTask{i} \times \TaskUBslot{i})$. 

\subsubsection*{Step 4: Tightening the analysis using sampling regions}
We further tighten the analysis by exploiting the task request-profiles, i.e., by using the information about the maximum number of requests in each of the constituent regions of the analyzed task. The region based analysis helps us to limit the range of the potential candidate slots for a set of requests. 
% For example, if the $r$'th request of $\tau_i$ is generated in the $k$'th region, then it \emph{cannot} be served in the $j$'th bus slot available to $\tau_i$ if $\Tmax{i}{j} < \SamplingRegionSize{i} \times (k-1)$, where $\SamplingRegionSize{i}$ is the size of the sampling interval. 
We  then define a range $[\LBslot{i}{k}, \UBslot{i}{k}]$ 
for each region $k$, which represent the first and last free bus slots in which requests from  region $k$ can be served, respectively. These bounds are employed by the proposed algorithm to tighten the analysis by defining a request-to-slot mapping for each individual region. The maximum delays incurred  by the requests of each region are computed successively and the overall WCET is subsequently computed. 
%Then, the resulting $C_i / \SamplingRegionSize{i}$ mappings are concatenated to arrive at the final solution. 
%The execution time of the task is updated to capture the computed maximum cumulative delay incurred by the requests in \emph{each} individual region and the final increased WCET is obtained at the end of the analysis of the last region of the given task. 
This process is described in detail in Section~\ref{sec:complexity_reduction}.
%Algorithm~\ref{alg:regAnalysis} is the focus of Section~\ref{sec:complexity_reduction}.

% we observe that the complexity $O(\NbReqPerTask{i} \times \TaskUBslot{i})$ may still be very large for tasks $\tau_i$ that can generate many requests (i.e $\NbReqPerTask{i}$ is large) and/or for tasks $\tau_i$ that can possible use many free bus slots (i.e. the bus is very often available to $\tau_i$, like for the highest priority task for example). 
% 
% To further reduce the complexity, we extend the bus availability model $\BusAvailability{i}$ with a set $\SetOfConstraints{i}$ of linear constraints on the range of free bus slots that a request of $\tau_i$ can possibly use. 
